/**
 * Created by L.jp
 * Description:链接：https://www.nowcoder.com/questionTerminal/f5805cc389394cf69d89b29c0430ff27
 * 来源：牛客网
 *
 * 给定一个长度为N(N>1)的整型数组A，可以将A划分成左右两个部分，左部分A[0..K]，右部分A[K+1..N-1]，K可以取值的范围是[0,N-2]。求这么多划分方案中，左部分中的最大值减去右部分最大值的绝对值，最大是多少？
 *
 * 给定整数数组A和数组的大小n，请返回题目所求的答案。
 * User: 86189
 * Date: 2022-04-24
 * Time: 15:57
 */
public class MaxGap {
    public static int findMaxGap(int[] A, int n) {
        //链接：https://www.nowcoder.com/questionTerminal/f5805cc389394cf69d89b29c0430ff27
        //来源：牛客网
        //
        //因为求的是两个最大值的差,所以肯定可以找到整个数组的最大值,然后就可以确定一边的最大值了,
        // 另一边的最大值就是要找左右两端最小那个数,因为无论他们怎么往外扩都只能增大,不能减小,所以最大差值就是第一次找出来的最大值和左右两边小的那个数的差了,
        //首先全局最大值一定在左半部分或者右半部分，另一个最大值就是在另一半的最小的最大值
        //全局最大值就是所有数中求出的最大值，还有一个最小的最大值就是在A【0】和A【n-1】中求出的最小值
        //因为无论怎么分，A【0】总是在左半部分第一个，A【n-1]总是在右半部分最后一个，所以另一个最大值就从他们两中取最小的那个
        int max=A[0];
        for(int i=1;i<n;i++){
            max=Math.max(max,A[i]);
        }
        return max-Math.min(A[0],A[n-1]);
    }
    
    public static void main(String[] args) {
        int[] A={1,2,3,4,5,6,7,8,9,10};
        int n=A.length;
        System.out.println(findMaxGap(A,n));
    }
}

